/*
 * Project: BoboDesignPattern
 * 
 * File Created at 2020年2月27日
 * 
 * Copyright 2012 Greenline.com Corporation Limited.
 * All rights reserved.
 *
 * This software is the confidential and proprietary information of
 * Greenline Company. ("Confidential Information").  You shall not
 * disclose such Confidential Information and shall use it only in
 * accordance with the terms of the license agreement you entered into
 * with Greenline.com.
 */
package test.lesson9.leetcode;

/**
 * @Type T2020227_53
 * @Desc 53. 最大子序和 难度 简单
 * 
 *       1672
 * 
 *       收藏
 * 
 *       分享 切换为英文 关注 反馈 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 
 *       示例:
 * 
 *       输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 进阶:
 * 
 *       如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
 * @author 52489
 * @date 2020年2月27日
 * @Version V1.0
 */
public class T2020227_53 {

    public static void main(String[] args) {
        int nums[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
        System.out.println(maxSubArray(nums));
        System.out.println(maxSubArray2(nums));
        System.out.println(maxSubArrayDP(nums));
        ;
    }

    // 暴力求解O（n）^3
    public static int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int sum;
        for (int i = 0; i < nums.length; i++) {// 子序列左端点
            for (int j = i; j < nums.length; j++) {// 子序列右端点
                sum = 0;
                String x = "";
                int kk = 0;
                for (int k = i; k <= j; k++) {// 暴力计算
                    kk = k;
                    sum += nums[k];
                    x = x + "," + nums[k] + "";
                }
                System.out.println("i=" + i + "_" + "j=" + j + "_" + "k=" + kk + "________" + x);
                if (sum > max) {
                    max = sum;
                }
            }
        }
        return max;
    }

    // 2.改进暴力法——时间效率O(N^2)
    // 其实我们可以发现，每次我们都是重复计算了一部分子序列，即当我计算前两个时，第三次我还是会计算前两个在加第三个，
    // 这样就造成了O(N^3)，现在我们根据前一次的进行计算，那么将会减少一层循环。

    public static int maxSubArray2(int[] nums) {
        int max = Integer.MIN_VALUE;
        int sum;
        for (int i = 0; i < nums.length; i++) {// 子序列左端点
            sum = 0;
            String x = "";
            for (int j = i; j < nums.length; j++) {// 子序列右端点
                sum += nums[j];// 这里就相当于每次根据前一次的序列来计算新的序列
                x = x + "," + nums[j] + "";
                if (sum > max)
                    max = sum;
            }
            System.out.println("i=" + i + "________" + x);
        }
        return max;
    }

    public static int maxSubArrayDP(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        if (nums.length == 1) {
            return nums[1];
        }

        int dp[] = new int[nums.length];
        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1; i < dp.length; i++) {
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + nums[i];
            } else {
                dp[i] = nums[i];
            }
            max = Math.max(dp[i], max);
        }

        return max;
    }

}
